import java.util.List;

/**
 * @author Sebastian
 * @version 2.0
 * @date 2024/5/30 20:59
 */
//重排链表
//给定一个单链表 L 的头节点 head ，单链表 L 表示为：
//
//L0 → L1 → … → Ln - 1 → Ln
//请将其重新排列后变为：
//
//L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
//不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
public class Solution143 {
    public void reorderList(ListNode head) {
        ListNode mid = findMiddleNode(head);
        ListNode head2 = reverse(mid);

        // 合并两个链表
        while (head2.next != null) {
            ListNode nxt = head.next;
            ListNode nxt2 = head2.next;
            head.next = head2;
            head2.next = nxt;
            head2 = nxt2;
            head = nxt;
        }
    }


    private ListNode reverse(ListNode head) {
        ListNode cur = head;
        ListNode prev = null;
        ListNode tmp = null;
        while (cur != null) {
            tmp = cur.next;
            cur.next = prev;
            prev = cur;

            cur = tmp;
        }
        return prev;
    }

    // 寻找中间节点
    private ListNode findMiddleNode(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}
